1. Field of the Invention
The invention relates to packet switching.
2. Related Art
In a packet-switched network, a xe2x80x9crouterxe2x80x9d is a device which receives packets on one or more input interfaces and which outputs those packets on one of a plurality of output interfaces, so as to move those packets within the network from a source device to a destination device. Each packet includes header information which indicates the destination device (and other information), and the router includes routing information which associates an output interface with information about the destination device (possibly with other information). The router can also perform other operations on packets, such as rewriting the packets"" headers according to their routing protocol or to reencapsulate the packets from a first routing protocol to a second routing protocol. It is advantageous for routers to operate as quickly as possible, so that as many packets as possible can be switched in a unit time.
One problem which has arisen in the art is that packets can be in one of a plurality of routing protocols or encapsulations, and can therefore include header information which the router needs to switch the packet (and to perform other operations on the packet) in locations which vary from packet to packet. This requires the router to be able to locate the header information in one or more of various locations within the packet. Thus, methods by which the router might operate relatively quickly can be inflexible with regard to the location for the header information, while methods by which the router might operate flexibly with regard to the location for the header information can be relatively slow.
Some known routers, such as those described in U.S. Pat. No. 5,509,006, xe2x80x9cApparatus and Method for Switching Packets Using Tree Memoryxe2x80x9d, issued Apr. 16, 1996, in the name of inventor Bruce A. Wilford, and assigned to cisco Systems, Inc., can determine a type for the packet and therefore the location of the header information, by examining each byte of the packet header in turn. Thus, each byte of the packet header provides information regarding interpretation of successive bytes of the packet header, and the router can determine the header information needed to switch the packet in response to the relatively early bytes of the packet header. While this method achieves the goal of being relatively flexible with regard to the location for the header information, it can take many clock cycles to determine the proper header information, and is therefore not as relatively quick as desired.
Accordingly, it would be desirable to provide a method and system for locating header information in packet headers and switching packets in response to that header information, which is both relatively quick and flexible with regard to location of the header information. This advantage is achieved in an embodiment of the invention in which header information recognizers operate in parallel on the packet header to determnine the location of the header information, and the packet is switched responsive to the header information so located.
The invention provides a method and system for identifying header information in a packet header, and for switching (and otherwise operating on) the packet in response thereto. A first set of header information recognizers operate in parallel on the packet header so as to recognize a header format for the packet header and to determine relevant header information in response to that header format. A second set of header information recognizers operates on the header information to select one or more sets of words from the header information which are used for one or more lookups for treatment of the packet.
In a preferred embodiment, the same or similar header information is located in the packet header responsive to information which determines an encapsulation type for the packet, such as packets which use the IP version 4, rP version 6, or IPX protocols. The header information can include the destination address for the packet, or some combination of the destination address and additional information; the additional information can include the sending address, the input interface, a number of bits matched for the destination address, or some combination thereof.